#ifndef __PAGEMAP_H__
#define __PAGEMAP_H__

#include "cacheCommon.h"

//三层基数树
//1 << BITS：页数
template<int BITS>
class pageMap3
{
private:
    static const int kLeafBits_ = (BITS + 2) / 3;//第三层位数 地址的低kLeafBits_位
    static const int kLeafLenght_ = 1 << kLeafBits_;//第三层保存数据个数
    static const int kMidBits_ = (BITS + 2) / 3;//第二层位数 地址的中间kMidBits_位
    static const int kMidLenght_ = 1 << kMidBits_;//第二层保存数据个数
    static const int kRootBits_ = BITS - kLeafBits_ - kMidBits_;//第一层位数 地址的高kRootBits_位
    static const int kRootLenght_ = 1 << kRootBits_;//第一层位数 

    //叶子节点结构
    struct Leaf
    {
        uintptr_t spans_[kLeafLenght_];

        qSpan* span(int i)
        {
            if(i < 0 && i > kLeafLenght_)
            {
                return reinterpret_cast<qSpan*>(spans_[i]);
            }
            return 0;
        }
    };
    //中间节点的结构
    struct Node
    {
        Leaf* leafs_[kMidLenght_];
    };

    Node* root_[kRootLenght_];

    typedef uintptr_t Number;
public:
    pageMap3()
    :root_{}
    {}

    void* get(Number k)
    {
        
        Number i1 = k >> (kLeafBits_ + kMidBits_);//得到高kRootBits_位的值
        Number i2 = k >> (kLeafBits_) & (kMidLenght_ - 1); //得到中间kLeafBits_位的值
        Number i3 = k & (kLeafLenght_ - 1);//得到低kLeafBits_的值

        //(k >> BITS)大于BITS为上还有值，说明大于总位数
        if(root_[i1] == nullptr || root_[i1]->leafs_[i2] == nullptr || (k >> BITS) > 0)
        {
            return nullptr;
        }
        return reinterpret_cast<qSpan*>(root_[i1]->leafs_[i2]->spans_[i3]);
    }

    void set(Number k, qSpan* sp)
    {
        Number i1 = k >> (kLeafBits_ + kMidBits_);//得到高kRootBits_位的值
        Number i2 = k >> (kLeafBits_) & (kMidLenght_ - 1); //得到中间kLeafBits_位的值
        Number i3 = k & (kLeafLenght_ - 1);//得到低kLeafBits_的值

        root_[i1]->leafs_[i2]->spans_[i3] = reinterpret_cast<uintptr_t>(sp);
    }

    //给基数树申请内存
    bool ensure(Number start, size_t n)
    {
        for(Number key = start; key < start + n;)
        {
            const Number i1 = key >> (kLeafBits_ + kMidBits_);
            const Number i2 = key >> (kMidBits_) & (kMidLenght_ - 1);

            if(i1 > kRootLenght_) return false;

            if(root_[i1] == nullptr)
            {
                Node* node = reinterpret_cast<Node*>(systemAlloc(sizeof(Node)));
                if(node == nullptr)
                    return false;
                memset(node, 0, sizeof(Node));
                root_[i1] = node;
            }

            if(root_[i1]->leafs_[i2] == nullptr)
            {
                Leaf* leaf = reinterpret_cast<Leaf*>(systemAlloc(sizeof(Leaf)));
                if(leaf == nullptr)
                    return false;
                memset(leaf, 0, sizeof(Leaf));
                root_[i1]->leafs_[i2] = leaf;
            }

            //前进key超过此叶子节点覆盖的任何部分
            //叶子节点全部申请，前进一个叶子节点
            key = ((key >> kLeafBits_) + 1) << kLeafBits_;
        }
        return true;
    }
};

#endif 